Interleaving String || Decode Ways

发表于

Interleaving String

Question

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:

s1 = "aabcc",

s2 = "dbbca",

When s3 ="aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

Analysis

中文题解

对于

s1 = a1, a2 ……..a(i-1), ai

s2 = b1, b2, …….b(j-1), bj

s3 = c1, c3, …….c(i+j-1), c(i+j)

定义 match[i][j] 意味着，S1的(0, i)和S2的(0,j)，匹配与S3的(i+j)

如果 ai == c(i+j), 那么 match[i][j] = match[i-1][j]， 等价于如下字符串是否匹配。

s1 = a1, a2 ……..a(i-1)

s2 = b1, b2, …….b(j-1), bj

s3 = c1, c3, …….c(i+j-1)

同理，如果bj = c(i+j), 那么match[i][j] = match[i][j-1];

转移方程如下：

1
2
3
4
5
6
7
8
9
10
Match[i][j]
    =   (s3.lastChar == s1.lastChar) && Match[i-1][j]
      ||(s3.lastChar == s2.lastChar) && Match[i][j-1]
初始条件：
    i=0 && j=0时，Match[0][0] = true;
    i=0时， s3[j] = s2[j], Match[0][j] |= Match[0][j-1]
           s3[j] != s2[j], Match[0][j] = false;
    j=0时， s3[i] = s1[i], Match[i][0] |= Match[i-1][0]
           s3[i] != s1[i], Match[i][0] = false;

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length())    return false;
        boolean[][] match=new boolean[s1.length()+1][s2.length()+1];
        match[0][0]=true;
        
        for(int i=1;i<=s1.length();i++){
            match[i][0]=match[i-1][0]&&s1.charAt(i-1)==s3.charAt(i-1);
        }
        
        for(int i=1;i<=s2.length();i++){
            match[0][i]=match[0][i-1]&&s2.charAt(i-1)==s3.charAt(i-1);
        }
        
        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                match[i][j]=(match[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1))||(match[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
            }
        }
        return match[s1.length()][s2.length()];
    }
}

Decode Ways

Question

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

Analysis

一开始考虑用一个数组来记录不同的组合数，后来发现当前i的decode way只与i-1、i-2的decode way个数有关，所以可以用r1,r2两个变量来记录。

  • 若字符i为0，由于此时字符i不能独立拆分，所以r1=0
  • 若当前字符可以之前字符组合，则r1=r1+r2,r2=r1（原）
  • 若当前字符不可组成字符组合，当前字符decode way个数不变，r1不变，r2向前移动（r2=r1）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int numDecodings(String s) {
        int r1=1,r2=1;  //r1 the decoding ways of str(i-1), r2 the decoding ways of str(i-2)
        if(s.length()==0||s.charAt(0)=='0') return 0;
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)=='0')    r1=0;
            
            if(s.charAt(i-1)=='1'||s.charAt(i-1)=='2'&&s.charAt(i)<'7'){
                int tmp=r1;
                r1=r1+r2;
                r2=tmp;
            }else{
                r2=r1;
            }
        }
        return r1;
    }
}